2-D clipping. --------------- "Don't discount flying pigs before you have good air defense." -- jvh@clinet.fi Screen boundaries clipping. --------------------------- Throughout the last chapter we've assumed that primitives we were rendering are completely within the screen boundaries. This is something we can't really guarantee. The worst thing- if we would try using those functions to render an element outside the screen, they won't much complain and would most likely try accessing memory outside the colourmap's allocated space. And I guess: segmentation fault, core dumped is hardly most graceful way to exit a program. So we don't have another choice but to guarantee rendering algorithms that the element passed is indeed inside the screen. A dot. ------ Clipping looks trivial in case of a dot, we just have to add few comparisons checking if the coordinates are in the screen range and proceed only if that is the case: void G_dot(int x,int y,unsigned char colour) { if( (x>=0)&&(x=0)&&(y ym = y2 - ----------------- x2-xm x2-x1 x2-x1 but this method involves multiplications and divisions, so beholding to our tradition let's try to avoid it. The alternative method is using binary search: A(-3,1) * | \ | (-1,3)* | o I(0,?) | \ | * B(1,5) | X=0 pic 4.4 Let's see how it works on a simple example: suppose we have to clip a line A(-3,1)-B(1,5) by an edge X=0 , we have to find Y of the intersection point. let's find midpoint of the line A-B: Ax+Bx Ay+By midx=------- midy=------- 2 2 midx=(-3+1)/2=-1 midy=(1+5)/2=3 Now, let's see where the boundary lies with respect to the midpoint? It is still to the right of it, so of two lines A-MidPoint MidPoint-B, edge intersects MidPoint-B. Let's rename MidPoint into A and start the midpoint search over again: midx=(-1+1)/2=0 midy=(3+5)/2=4 Here, the intersection came precisely onto the edge. So midy is the Y coordinate of Intersection point we were looking for. It appears that this method involve a lot of calculations, but they are all very cheap, just an addition and division by two (which is actually a 1 bit right shift). Practice shows binary search works indeed faster then calculation resulting from solving similar triangles. When dealing with divisions performed by shits however, one has to be aware of truncation problems that might arise. Since -1>>1=-1 that means that if we would try to use algorithm described above to clipp (-1,y1)-(0,y2) line by X==0 boundary chances are we would loop forever, at each iteration finding that -1>>1 is still -1. (and O(for ever) is hardly, the time complexity contributing towards high frame-rate). As in the code below this situation should be thought of. Let's create a function which would perform clipping against two vertical screen edges: that is C_X_CLIPPING_MIN and C_X_CLIPPING_MAX. int C_line_x_clipping(int **vertex1,int **vertex2,int dimension) { register int i; register int whereto; register int *l,*r,*m,*t; /* left right and midle and tmp */ static int g_store0[C_MAX_DIMENSIONS]; /* static stores for clipped vxes */ static int g_store1[C_MAX_DIMENSIONS]; static int g_store2[C_MAX_DIMENSIONS]; static int g_store3[C_MAX_DIMENSIONS]; static int g_store4[C_MAX_DIMENSIONS]; static int g_store5[C_MAX_DIMENSIONS]; int **vmn,**vmx; /* so that *vmn[0] < *vmx[0] */ int swap; /* we coordinates swaped? */ C_2D_clipping=0; /* default no clipping yet */ if((*vertex1)[0]<(*vertex2)[0]) { swap=0; vmn=vertex1; vmx=vertex2; } /* so that *vmn[0] < *vmx[0] */ else { swap=1; vmn=vertex2; vmx=vertex1; } if(((*vmn)[0]>C_X_CLIPPING_MAX)||((*vmx)[0]>1; whereto=m[0]=C_X_CLIPPING_MAX) /* clipping */ { HW_copy_int(*vmn,l=g_store3,dimension); /* copying old vertixes */ HW_copy_int(*vmx,m=g_store4,dimension); r=g_store5; /* let middle be here */ whereto=0; while(m[0]!=C_X_CLIPPING_MAX) { if(whereto==1) { t=l; l=m; m=t; } else { t=r; r=m; m=t; } for(i=0;i>1; whereto=m[0] r | | | v v v +---------+ +---------+ +---------+ |x,y,z... | |x,y,z... | |x,y,z... | +---------+ +---------+ +---------+ pic 4.5 This is being done so that at every iteration only pointers to actual data are moved not the data itself. (The point I am trying to make: (and I am sure everybody knows that, just a bit of reinforcement) it's ok to physically copy small amounts of data, but when we have a lot of it, it is better to move pointers instead) Let's insert calls to clipping function into the G_line routine: ... ... v1=vertex1; v2=vertex2; if(C_line_x_clipping(&v1,&v2,2)) /* horizontal clipping */ { if(C_line_y_clipping(&v1,&v2,2)) /* vertical clipping */ { dx=v2[0]-v1[0]; dy=v2[1]-v1[1]; /* ranges */ ... ... So, whenever line is completely clipped we wouldn't go any further in the rasterization function. A polygon. ---------- Now, remembering that we render polygon by scanning it's edges using rasterization function pretty much like the one above, we may think that adding clipping calls into GI_scan would solve our problem with polygon clipping, unfortunately, it is only half true (literary half true). Lets consider pictures pic 4.6 and 4.7: B * B | *==== I/ |/==== -----*------ I*====== /====== /|?????? /======== / |????? /======== A* |?????? A*========== pic 4.6 pic 4.7 In the cases above edge A-B contribute to the left side of the polygon, clipping present no problem for case on pic 4.7. Clipped part I-B of the edge can be discarded since there's nothing to form outside the screen. On the other hand in the case on pic 4.6 we can't simply discard clipped part A-I since we would loose left boundary of all horizontal lines marked "???". The observation we can make is that polygon, being scanned edge at a time, may not be clipped against horizontal boundaries but must be clipped against vertical, this way the code within GI_scan would look like: ... ... v1=edges; edges+=skip; v2=edges; /* length ints in each */ if(C_line_y_clipping(&v1,&v2,dimension)) /* vertical clipping */ { dx=*v2++; dy=*v2++; /* extracting 2-D coordinates */ x=*v1++; y=*v1++; /* v2/v1 point remaining dim-2 */ ... ... Creating a vertically clipped polygon on the other hand is a bit more complicated. The problem is that the clipped polygon may have different from the original one number of edges. let's consider the situation on the pic 4.8: /* 3 | | / | |5' |/ | 5*-*-----*6 * | / | \ /|2''| 4* | *1 2 * | | \ | / \| | 3*-*-----*2 *\ | |3' |2'\* 1 pic 4.8 pic 4.9 It can be seen that original polygon has 6 edges which becomes 5 after clipping. Some other polygon pic 4.9 can have 1 more edge after clipping. It is obvious that we would have to create a temporary structure to hold the clipped polygon. Now, we know how to clip a single edge, let's try to find pattern how clipped edges compose clipped polygon. Let's be considering clipping against a single boundary, say X==0. it is obvious that if an edge is completely outside it's vertexes won't be present in the new polygon. On the other hand if an edge is within the boundary both points would be present. Any point on the intersection line would be present too. One more consideration is that each point in the polygon belong to two edges, so when the edge is not clipped we may put into the new structure just the second point assuming that the first one is already taken care of when we were processing previous edge. Let's list the patterns: (1) If edge is not clipped or the second point is clipped put into new structure just the second point; (2) When first point is changed or both are changed put both; (3) When both are outside put none. Surprisingly enough this algorithm doesn't have to be changed when we consider simultaneous clipping against two parallel boundaries: | *-----*1| |/5 \| 4'* *2' /| |\ 4* | | \ | | | \ *-*---------*---*2 3 |3' |2'' | | pic 4.10 edge 1-2 Second point clipped - pattern (1) putting in 2' edge 2-3 Both points changed - pattern (2) putting in 2'' and 3' edge 3-4 Both points outside - pattern (3) ignoring edge 4-5 First point clipped - pattern (2) putting in 4' and 5 edge 5-1 No clipping - pattern (1) putting in 1 The result is: 2'-2''-3'-4'-5-1 just looking at the picture assures us that what we got is indeed right. Now finally the purpose of C_2D_clipping variable being set in C_line_x_clipping must be clear. It would be set to 1 whenever first or both points were changed, and would be 0 if none or just second one were changed. Knowing this all let's write some code: int C_polygon_x_clipping(register int *from,register int *to, int dimension,int length ) { register int i; int *v1,*v2,new_lng=0; int *first_vrtx=to; /* begining of the source */ for(i=0;i *-------------> *--------------------------> A*- - -> -----I-----I----- pic 4.12 By applying perspective transformation we increase the absolute values of coordinate components depending on inverse of it's distance to the viewer, so if Z==0 transforms into infinity numbers close to that transform into something bitsize of numbers stored in computers might not be able to handle, and no, we can't quite solve it by moving the clipping plane slightly forward, since there are still those nasty points which are slightly in front of the viewing plane but already have big absolute value of X or Y. (pic 4.12, point A). The overflow problem that may result from perspectively transforming this point is this: positive values may become negative, and if it would happen to just one point of two off-screen points representing a line we may actually see this line all across the screen instead of not seeing it at all. The conclusion when using perspective transformation, it is better to apply it to the points we know would produce a valid result. And since what we ultimately want is to project to the screen we are coming back to the view volumes since those are exactly sets of points that would be projected inside the screen. Hence we do need to consider actual viewing volume for perspective projection. What the view volume for perspective projection would look like? The way we modeled this transformation - rays of all visible points converge in viewer's eye. If we would cast back into space lines connecting the eye and the screen boundaries, we would obtain the pyramid marking points from space that would project onto screen edges. what's inside the pyramid would project inside the screen what's outside - outside the screen. adding the clipping plane somewhere in front of the viewer we are obtaining the view-volume for perspective projection, pic 4.13. \ / \ / \ / \ / \ / -----I\---/I----- \ / * pic 4.13 The only problem - we now have to clip against planes which are directed almost arbitrary in space (the exact geometry of this view volume depends on the "focus" parameter - the distance between the viewer and the viewing plane (again, not quite the same as clipping plane). Although conceptually easy to achieve clipping against arbitrary directed plane would have higher complexity. There is number of solutions one can consider: obvious one: indeed implement real volume clipping, although expansive we would be able to completely get rid of 2-D clipping routines which overall might be quite descent. Second: implement volume clipping with special kind of perspective view volume, the one having 90' angle. The reason can be seen from the pic 4.14: \ / \ / x=-z \ / x=z \ / ----I\-----/I----- \ / * pic 4.14 Planes composing this perspective view volume have pretty simple equations: x==z , y==z, x==-z and y==-z clipping against those is way easier then against arbitrary directed planes. The method however we would discuss is a bit different, that is, we would not do clipping at all, to be more exact we would only throw away polygons which are for sure outside the view volume and leave those even partially inside to be further clipped against screen boundaries after being projected. ( Clipping against viewing plane, is a sacred matter that one can hardly get rid of ) One should understand that this method works on assumption that there is no terribly big polygons around, since a one part of a really big polygon can be within the view volume whereas another can be both close to viewing plane and have really big absolute value of X or Y, just something we are trying to exclude from being perspectively projected. How can one figure out whether a point is outside the pyramid with 90' angle? From the pic 4.14 we can see that parts of the space separated by Z==X and Z==-X planes have obvious relationships among X and Z of every point, if Z-X | Z>X / \ | / A *---------------------* B \ | / Z<-X \ / Z X pic 4.15 We would make decisions, on the other hand, using notion of polygon's extends. pic 4.16 Extend is a cube completely enclosing within itself certain polygon. So coordinates of extend planes are that of maximum and minimum among the polygon vertices along all axes. xmin xmax -------------- ymin |\\ | | \ \ | | \ \ | | \ /| | \/ | |------------ ymax pic 4.16 This way by considering for example (xmin,zmax) point of the extend box we can make a decision whether polygon's extend is outside the x=z plane. ^ Z | \ | / \ | / (xmax,zmax) \ | / (xmin,zmax) ----+ \ | / +----+ | \ | / | --+ \ / +--- --------------*-----------------> X +-------+ (zmax) | | pic 4.17 Let's list all the other cases: xmin > zmax ymin > zmax -xmax > zmax -ymax > zmax On the same stage we can check if the polygon is completely behind the view plane as well. int C_volume_clipping(register int *vxes,int number) { int xmin,ymin,zmin,xmax,ymax,zmax; int i; ymin=xmin=zmin=INT_MAX; ymax=xmax=zmax=INT_MIN; /* initializing searching */ for(i=0;ixmax) xmax=*vxes; if(*vxesymax) ymax=*vxes; if(*vxeszmax) zmax=*vxes; if(*vxes